package com.huawei.java.main;


import com.huawei.java.pojo.*;

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.*;
//import com.huawei.java.zother.Timer;

/**
 * @author 金昊霖
 */
public final class Main {
    /**
     * 购买策略变化因子，如果剩余资源超过此值，则对其重新规划策略(此数值是动态在遍的)
     */
    static int purchaseBorder;

    /**
     * 内核内存比（会动态变化）
     */
    static double ratio;
    /**
     * 服务器类型Map集合（方便用字符查找）
     */
    static Map<String, ServerType> serverTypes;
    /**
     * 虚拟机类型Map集合
     */
    static Map<String, VirtualMachineType> virtualMachineTypes;
    /**
     * 请求队列
     */
    static List<AddRequest>[] addRequestQueue;

    /**
     * 未完成请求剩余数
     */
    static int[] remainNum;

    /**
     * 删除请求
     */
    static Map<Integer,DeleteRequest>[] deleteRequestQueue;

    /**
     * 迁移的请求
     */
    static List<MigratingRequest>[] migratingRequestQueue;

    /**
     * 购买请求
     */
    static List<SimpleServerType>[] purchaseServers;
    /**
     * 服务器集合，序号便是服务器id（非真实）
     */
    static List<Server> servers=new ArrayList<>(5000);

    static List<Integer>[] virtualMachineIds=new LinkedList[7000];
    /**
     * 记录服务器真实id(如果服务器大于7500，gg)
     */
    static int[] serversIds =new int[10000];

    /**
     * 虚拟机集合
     */
    static Map<Integer, VirtualMachine> virtualMachines;

    /**
     * 按服务器内核内存比进行升序的服务器类型
     */
    static List<ServerType> sortedServerTypes;

    static List<VirtualMachine> unbalancedVirtualMachines=new LinkedList<>();


    public static void main(String[] args) {
        innit();
//        Timer.start();
        for (int i = 0; i< addRequestQueue.length; i++){
            //第一次不用迁移和部署
            if (i!=0){
                //当前虚拟机存量的千分之五（向下取整）
                int size= (int) (virtualMachines.size()*0.005);
                //迁移，整理资源
                migrate(i,size);
//                System.out.println("第"+i+"天迁移耗时：");
//                Timer.print();
                //对请求进行部署
                deploy(i);
//                System.out.println("第"+i+"天部署耗时：");
//                Timer.print();
            }
            purchase(i);
//            System.out.println("第"+i+"天购买耗时：");
//            Timer.print();
        }
        out();
    }


    /**
     * 初始化数据集
     */
    private static void innit(){
        //所有的虚拟机数量
        int num=0;
        InputReader in = new InputReader();
        //读入采购服务器类型数量
        int n= in.nextInt();
        //初始化服务器类型集合和排序好的服务器类型集合(尽量让map不扩容，扩容因子默认是0.75)
        serverTypes=new HashMap<>((int)(n/0.75+1.0));
        //初始化服务器类型
        sortedServerTypes=new ArrayList<>(n);
        String[] strings;
        ServerType serverType;
        for (int i=0;i<n;i++){
            strings=in.nextLine().split("\\(|, |\\)");
            serverType=new ServerType(strings);
            serverTypes.put(strings[1],serverType);
            sortedServerTypes.add(serverType);
        }
        //读入虚拟机类型数量
        n=in.nextInt();
        //初始化虚拟机类型集合(尽量让map不扩容，扩容因子默认是0.75)
        virtualMachineTypes=new HashMap<>((int)(n/0.75+1.0));
        for (int i=0;i<n;i++){
            strings=in.nextLine().split("\\(|, |\\)");
            virtualMachineTypes.put(strings[1],new VirtualMachineType(strings));
        }
        //读入请求天数
        n=in.nextInt();
        //初始化请求队列
        addRequestQueue = new List[n];
        //初始化未完成请求数数组
        remainNum=new int[n];
        //初始化迁移请求队列
        migratingRequestQueue =new List[n];
        //初始化购买服务器队列
        purchaseServers=new List[n];
        deleteRequestQueue=new LinkedHashMap[n];
        VirtualMachineType vt;
        for (int i=0;i<n;i++){
            //每天的请求数
            int m=in.nextInt();
            //初始化每天的请求队列
            addRequestQueue[i]=new ArrayList<>(m);
            deleteRequestQueue[i]=new LinkedHashMap<>((int)(m/0.75+1.0));
            remainNum[i]=m;

            for (int j=0;j<m;j++){
                strings=in.nextLine().split("\\(|, |\\)");
                if ("add".equals(strings[1])){
                    vt=virtualMachineTypes.get(strings[2]);
                    num++;
                    addRequestQueue[i].add(new AddRequest(j,Integer.parseInt(strings[3]),vt));
                }else {
                    deleteRequestQueue[i].put(Integer.valueOf((strings[2])),new DeleteRequest(j,Integer.parseInt(strings[2])));
                }
            }
            //对每天的增加请求进行从大到小排序
            Collections.sort(addRequestQueue[i]);
        }
        //初始化虚拟机集合
        virtualMachines=new HashMap<>((int) (num/0.75+1.0));
    }

    /**
     * 对虚拟机进行迁移（就是对那些导致不平衡的虚拟机进行迁移）
     * @param day 当前天数-1（即从0开始）
     * @param size 当前最多能迁移虚拟机的数量
     */
    private static void migrate(int day,int size){
        //是否开启全部迁移
        boolean isAll=addRequestQueue[day].size()<deleteRequestQueue[day].size();
        //初始化当天的迁移请求队列
        migratingRequestQueue[day]=new ArrayList<>(size);
        //如果迁移数为0，则直接退出
        if (size==0){
            return;
        }
        //当前迁移的次数
        int num=0;
        Integer flag = null;
        Server server;
        VirtualMachine virtualMachine;
        ListIterator<VirtualMachine> vll=unbalancedVirtualMachines.listIterator();
        ListIterator<Integer> ill;
        int node;
        //标记map,只有全部迁移才需要用到
        Map<Integer,Integer> flagMap=null;
        //初始化标记map
        flagMap=new HashMap<>((int) (size/0.75+1.0));
        //将导致不平衡的虚拟机迁移
        while (vll.hasNext()){
            if (num>=size){
                return;
            }
            virtualMachine=vll.next();
            //先把迁移前的节点记录下来
            node=virtualMachine.getNode();
            //该虚拟机存在的服务器
            server=servers.get(virtualMachine.getServerId());
            //如果此请求已经被删除或者其所在的节点已经平衡，移除即可，跳到下一个
            if (virtualMachines.get(virtualMachine.getId())==null||server.simpleCheck(node)){
                vll.remove();
                continue;
            }
            for (Server s:servers){
                //如果在不在同一台服务器
                if (s.getId()!=virtualMachine.getServerId()){
                    flag=s.balancedAddVirtualMachine(virtualMachine,virtualMachineIds[s.getId()]);
                    if (flag!=null){
                        server.deleteVirtualMachine(virtualMachine,node,virtualMachineIds[server.getId()]);
                        //添加到迁移队列
                        migratingRequestQueue[day].add(new MigratingRequest(virtualMachine.getId(), virtualMachine.getServerId(),virtualMachine.getNode()));
                        num++;
                        //从不平衡集合中删除
                        vll.remove();
                        break;
                    }
                }
            }
        }
        if (num>=size){
            return;
        }
        if (isAll){
            List<SimpleServer> simpleServers=new ArrayList<>(servers.size());
            for (int i=servers.size()-1;i>=0;i--){
                simpleServers.add(new SimpleServer(i,virtualMachineIds[i].size()));
            }
            //对该集合中虚拟机数量进行升序排序
            Collections.sort(simpleServers);
            //这里记录满了的服务器id
            int fullSimpleServerId =simpleServers.size()-1;
            int serverId;
            Server s;
            for (int i = 0; i< fullSimpleServerId; i++){
                serverId=simpleServers.get(i).getServerId();
                server=servers.get(serverId);
                ill=virtualMachineIds[serverId].listIterator();
                while (ill.hasNext()){
                    if (num>=size){
                        return;
                    }
                    virtualMachine=virtualMachines.get(ill.next());
                    //如果此请求在标记map中，则说明此虚拟机已经迁移，已经到了最优解，或者要迁移的虚拟机在删除请求中存在，跳过即可
                    if (flagMap.get(virtualMachine.getId())!=null||deleteRequestQueue[day].get(virtualMachine.getId())!=null){
                        continue;
                    }
                    //记录原本部署的节点
                    node=virtualMachine.getNode();
                    for (int j = fullSimpleServerId; j>i; j--){
                        s=servers.get(simpleServers.get(j).getServerId());
                        if (s.isAisFull()&&s.isBisFull()){
                            //之前的服务器已经满了
                            if (fullSimpleServerId ==j){
                                //说fullServerId之后的服务器都已经满了无需再遍历，该数+1
                                fullSimpleServerId--;
                            }
                            continue;
                        }
                        flag=s.balancedAddVirtualMachine(virtualMachine,virtualMachineIds[s.getId()]);
                        if (flag!=null){
                            server.simpleDeleteVirtualMachine(virtualMachine,node);
                            //在外部删除
                            ill.remove();
                            migratingRequestQueue[day].add(new MigratingRequest(virtualMachine.getId(), virtualMachine.getServerId(),virtualMachine.getNode()));
                            num++;
                            //加入标记map
                            flagMap.put(virtualMachine.getId(),1);
                            break;
                        }
                    }
                    //如果此台服务器有请求无法迁移，则放弃迁移此台服务器
                    if (flag==null){
                        break;
                    }
                }
            }
        }

    }




    /**
     * 根据请求队列购买服务器,这里也包含了将剩余的请求进行部署
     * @param day 第几天（第一天为0）
     */
    private static void purchase(Integer day){
        //排序
        for (ServerType st:sortedServerTypes){
            st.updatePerformance(addRequestQueue.length-day);
        }
        sortedServerTypes.sort(Comparator.comparingInt(ServerType::getPerformance));
        //记录此时的计数器数字
        int count= Server.getCount();
        purchaseServers[day]=new ArrayList<>(16);
        //获取最优比的服务器类型
        ServerType currentType;
        Server server;
        boolean flag;
        while (remainNum[day]!=0){
            //选出适合的服务器
            currentType=choose(day);
            server=new Server(currentType);

            virtualMachineIds[server.getId()]=new LinkedList<>();
            servers.add(server);
            //部署
            simpleDeploy(day,server);
            flag=false;
            //将服务器加入购买队列
            for (SimpleServerType sst:purchaseServers[day]){
                if (sst.getName().equals(currentType.getName())){
                    sst.getServerIds().add(server.getId());
                    flag=true;
                    break;
                }
            }
            if (!flag){
                purchaseServers[day].add(new SimpleServerType(currentType.getName(),server.getId()));
            }
        }
        //遍历服务器购买集合，将真正的服务器id写入入
        for (SimpleServerType sst:purchaseServers[day]){
            for (Integer i:sst.getServerIds()){
                serversIds[i]=count++;
            }
        }
    }

    /**
     * 输出结果
     */
    private static void out(){
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)),true);
        int size;
        for (int i=0;i<addRequestQueue.length;i++){
            //对当天请求队列排序
            addRequestQueue[i].sort(Comparator.comparingInt(AddRequest::getNumber));
            //输出购买
            size=purchaseServers[i].size();
            out.println("(purchase, "+size+")");
            for (SimpleServerType sst:purchaseServers[i]){
                out.println("("+sst.getName()+", "+sst.getServerIds().size()+")");
            }
            //输出迁移操作
            if (i==0){
                out.println("(migration, 0)");
            }else {
                out.println("(migration, "+ migratingRequestQueue[i].size()+")");
                for (MigratingRequest r: migratingRequestQueue[i]){
                    if (r.getNode()==0){
                        out.println("("+r.getVirtualMachineId()+", "+serversIds[r.getServerId()]+")");
                    }else if (r.getNode()==1){
                        out.println("("+r.getVirtualMachineId()+", "+serversIds[r.getServerId()]+", A"+")");
                    }else {
                        out.println("("+r.getVirtualMachineId()+", "+serversIds[r.getServerId()]+", B"+")");
                    }
                }
            }

            //输出部署操作
            for(AddRequest r:addRequestQueue[i]){
                if (r.getNode()==0){
                    out.println("("+serversIds[r.getServerId()]+")");
                }else if (r.getNode()==1){
                    out.println("("+serversIds[r.getServerId()]+", A"+")");
                }else {
                    out.println("("+serversIds[r.getServerId()]+", B"+")");
                }
            }
        }
    }

    /**
     * 将requests里的请求依次部署到servers上
     * @param day 当前天数
     */
    private static void deploy(final int day){
        for (Server s:servers){
            if (remainNum[day]==0){
                return;
            }
            //部署前更新策略
            updateStrategy(day);
            simpleDeploy(day,s);
        }
    }

    /**
     * 将请求部署到一台服务器上，要注意执行此次部署时，为执行的删除请求所对应的虚拟机都还没部署，即增加请求并未部署完
     * @param day 当前天数
     * @param server 服务器
     * @return result 返回此次部署的虚拟机数量
     */
    private static int simpleDeploy(final int day, Server server){
        if (remainNum[day]==0){
            return 0;
        }
        int result=0;
        VirtualMachine virtualMachine ;
        //添加标记，表示是否成功加入，其值代表部署的节点
        Integer flag;
        for (AddRequest ar:addRequestQueue[day]){
            //如果该请求未被处理
            if (ar.getServerId()==null){
                virtualMachine=new VirtualMachine(ar.getVirtualMachineId(),ar.getVirtualMachineType());
                flag=server.balancedAddVirtualMachine(virtualMachine,virtualMachineIds[server.getId()]);
                if (flag!=null){
                    ar.setServerId(server.getId());
                    ar.setNode(flag);
                    virtualMachines.put(virtualMachine.getId(), virtualMachine);
                    remainNum[day]--;
                    result++;
                }
            }
        }
        //非平衡部署
        for (AddRequest ar:addRequestQueue[day]){
            //如果该请求未被处理
            if (ar.getServerId()==null){
                virtualMachine=new VirtualMachine(ar.getVirtualMachineId(),ar.getVirtualMachineType());
                flag=server.addVirtualMachine(virtualMachine,virtualMachineIds[server.getId()]);
                if (flag!=null){
                    ar.setServerId(server.getId());
                    ar.setNode(flag);
                    virtualMachines.put(virtualMachine.getId(), virtualMachine);
                    remainNum[day]--;
                    result++;
                    unbalancedVirtualMachines.add(virtualMachine);
                }
            }
        }
        //初始化virtualMachine
        virtualMachine =null;
        DeleteRequest dr;
        for (Map.Entry<Integer, DeleteRequest> entry : deleteRequestQueue[day].entrySet()) {
            dr= entry.getValue();
            //如果已经执行过，直接跳过
            if (dr.isComplete()) {
                continue;
            }
            //该删除请求对应的虚拟机
            virtualMachine = virtualMachines.get(dr.getVirtualMachineId());
            //此时要删除的虚拟机已经部署，删除它即可
            if (virtualMachine != null && virtualMachine.getServerId().equals(server.getId())) {
                server.deleteVirtualMachine(virtualMachine, virtualMachine.getNode(), virtualMachineIds[server.getId()]);
                //标记其已经执行
                dr.setComplete(true);
                virtualMachines.remove(virtualMachine.getId());
                remainNum[day]--;
            }
            //如果此删除操作在上一步执行
            if (dr.isComplete()) {
                //遍历当日增加请求，寻找是否有未部署且在该删除之后的请求,尝试将虚拟机添加到该服务器
                for (AddRequest ar : addRequestQueue[day]) {
                    if (ar.getServerId() == null && ar.getNumber() > dr.getNumber()) {
                        //创建对应虚拟机
                        virtualMachine = new VirtualMachine(ar.getVirtualMachineId(), ar.getVirtualMachineType());
                        flag = server.balancedAddVirtualMachine(virtualMachine, virtualMachineIds[server.getId()]);
                        if (flag != null) {
                            ar.setServerId(server.getId());
                            ar.setNode(flag);
                            virtualMachines.put(virtualMachine.getId(), virtualMachine);
                            remainNum[day]--;
                            result++;
                        }
                    }
                }
                //非平衡部署
                for (AddRequest ar : addRequestQueue[day]) {
                    if (ar.getServerId() == null && ar.getNumber() > dr.getNumber()) {
                        //创建对应虚拟机
                        virtualMachine = new VirtualMachine(ar.getVirtualMachineId(), ar.getVirtualMachineType());
                        flag = server.addVirtualMachine(virtualMachine, virtualMachineIds[server.getId()]);
                        if (flag != null) {
                            ar.setServerId(server.getId());
                            ar.setNode(flag);
                            virtualMachines.put(virtualMachine.getId(), virtualMachine);
                            remainNum[day]--;
                            result++;
                            //加入不平衡虚拟机集合
                            unbalancedVirtualMachines.add(virtualMachine);
                        }
                    }
                }
            }
        }
        return result;
    }
    /**
     * 对未部署的请求进行规划预计规模
     * @param day 当前天数
     * @return result 返回合适服务器类型
     */
    private static ServerType choose(int day){
        int cores1=0;
        int cores2=0;
        int memory1=0;
        int memory2=0;
        int minDifference = -1;
        int difference;
        int maxCore;
        int maxMemory;
        ServerType bestServerType=null;
        ServerType serverType ;
        VirtualMachineType vt;
        for (AddRequest ar:addRequestQueue[day]){
            if (ar.getServerId()==null){
                vt= ar.getVirtualMachineType();
                if (vt.getType()==1){
                    cores1+=vt.getCores()>>1;
                    cores2 +=vt.getMemory()>>1;
                    memory1+=vt.getMemory()>>1;
                    memory2+=vt.getMemory()>>1;
                }else {
                    if (cores1+memory1< cores2 +memory2){
                        cores1+=vt.getCores();
                        memory1+=vt.getMemory();
                    }else {
                        cores2 +=vt.getCores();
                        memory2+=vt.getMemory();
                    }
                }
                maxCore= Math.max(cores1,cores2)*2;
                maxMemory=Math.max(memory1,memory2)*2;
                serverType=null;
                //选出符合的条件且花费最低的服务器类型
                for (ServerType st:sortedServerTypes){
                    if (st.getCores()>maxCore&&st.getMemory()>maxMemory){
                        serverType=st;
                        break;
                    }
                }
                if (serverType==null){
                    break;
                }
                difference=serverType.getCores()-cores1-cores2+serverType.getMemory()-memory1-memory2;
                if (minDifference==-1||minDifference>difference){
                    minDifference=difference;
                    bestServerType=serverType;
                }
            }

        }
        return bestServerType;
    }

    /**
     * 从最佳内核内存比下标扩散，寻找资源符合的服务器类型中
     * @param day 当前天数
     * @param i 最佳内核内存比的服务器类型下标
     * @return result result[0]表示类型下标，result[1]表示服务器id
     */
    private static int[] choseBySource(int day,int i){
        int[] result=new int[2];
        int left;
        int right;
        int size=sortedServerTypes.size();
        Server server;
        for (int n=1;n<size;n++){
            left=i-n;
            right=i+n;
            if (left>=0){
                server=new Server(sortedServerTypes.get(left));
                if (simpleDeploy(day,server)!=0){
                    //加入服务器集合
                    servers.add(server);
                    result[0]=left;
                    result[1]=server.getId();
                    return result;
                }
                //回退计数器
                Server.setCount(Server.getCount()-1);
            }
            if (right<size){
                server=new Server(sortedServerTypes.get(right));
                if (simpleDeploy(day,server)!=0){
                    //加入服务器集合
                    servers.add(server);
                    result[0]=right;
                    result[1]=server.getId();
                    return result;
                }
                Server.setCount(Server.getCount()-1);
            }
        }
        //不可能发生的情况，题目规定肯定有一种服务器能部署
        return null;
    }

    /**
     * 更新策略
     * @param day 天数
     */
    private static void updateStrategy(final int day){
        int totalCores=0;
        int totalMemory=0;
        int num=0;
        List<AddRequest> addRequests=addRequestQueue[day];
        VirtualMachineType type;
        //对请求的规模进行预估
        for (AddRequest ar:addRequests){
            //如果该请求是未执行的请求
            if (ar.getServerId()==null){
                type=ar.getVirtualMachineType();
                totalCores+=type.getCores();
                totalMemory+=type.getMemory();
                num++;
            }
        }
        if (num==0){
            return;
        }
        ratio=1.0*totalCores/totalMemory;
        //修改购买平衡因子
        purchaseBorder=(int)((totalCores+totalMemory)/num*0.22);
        //修改服务器平衡因子，调整服务器的平衡策略
        Server.balanceFactor=ratio;
        Server.balanceBorder=purchaseBorder;
    }
}